package me.mingshan.leetcode;

/**
 *https://leetcode.cn/problems/delete-the-middle-node-of-a-linked-list/description/
 *
 * 删除链表的中间节点
 *
 * 给你一个链表的头节点 head 。删除 链表的 中间节点 ，并返回修改后的链表的头节点 head 。
 *
 * 长度为 n 链表的中间节点是从头数起第 ⌊n / 2⌋ 个节点（下标从 0 开始），其中 ⌊x⌋ 表示小于或等于 x 的最大整数。
 *
 * 对于 n = 1、2、3、4 和 5 的情况，中间节点的下标分别是 0、1、1、2 和 2 。
 *
 * @author hanjuntao
 * @date 2025/8/5 0005
 */
public class L_2095_删除链表的中间节点 {

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(3);
        ListNode node3 = new ListNode(4);
        ListNode node4 = new ListNode(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        ListNode result = deleteMiddle(node1);
        ListNode.print(result);
    }

    /**
     * 思路：
     *
     * 1. 获取链表的长度
     * 2. 获取中间节点的索引
     * 3. 找到中间节点,然后将其删除
     *
     * @param head
     * @return
     */
    public static ListNode deleteMiddle(ListNode head) {
        int count = 0;

        ListNode curr = head;
        while (curr != null) {
            count++;
            curr = curr.next;
        }

        // 中间指针，从0开始
        int middle = count / 2;

        ListNode pre = null;
        curr = head;

        int index = 0;

        while (curr != null) {
            ListNode next = curr.next;
            if (index == middle) {
                if (pre == null) {
                    head = next;
                } else {
                    pre.next = next;
                }
                curr.next = null;
                break;
            }

            pre = curr;
            curr = next;
            index++;
        }

        return head;
    }
}
